package org.example;

import java.util.*;
import java.util.Arrays;

// 二叉树练习题
// https://labuladong.online/algo/problem-set/binary-tree-traverse-i/
public class BinaryTree1 {
    // 257. 二叉树的所有路径
    // 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
    // 叶子节点 是指没有子节点的节点。
    // 示例 1：
    // 输入：root = [1,2,3,null,5]
    // 输出：["1->2->5","1->3"]

    // 基本思路
    // 前文手把手刷二叉树总结篇说过二叉树的递归分为[遍历]和[分解问题]两种思维模式，这道题需要用到[遍历]的思维。
    // 你让我求所有根节点到叶子节点的路径，那我遍历一遍二叉树肯定可以搞定，遍历到叶子节点的时候想办法把路径生成出来就行了。
    static class BinaryTreePaths {
        // 记录traverse函数递归时的路径
        LinkedList<String> path = new LinkedList<>();
        // 记录所有从根节点到叶子节点的路径
        LinkedList<String> res = new LinkedList<>();

        public List<String> binaryTreePaths(TreeNode root) {
            // 遍历一遍二叉树就能出结果了
            traverse(root);
            return res;
        }

        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // root是叶子节点
            // 收集结果，根据下一层判断
            if (root.left == null && root.right == null) {
                path.addLast(root.val + "");
                // 将这条路径转入res
                res.addLast(String.join("->", path));
                path.removeLast();
                return;
            }
            // 前序遍历位置
            path.addLast(root.val + "");
            // 递归遍历左右子树
            traverse(root.left);
            traverse(root.right);
            // 后序遍历位置
            path.removeLast();
        }
    }

    // 129. 求根节点到叶节点数字之和
    // 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
    // 每条从根节点到叶节点的路径都代表一个数字：
    // 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
    // 计算从根节点到叶节点生成的 所有数字之和 。
    // 叶节点 是指没有子节点的节点。
    // 输入：root = [1,2,3]
    // 输出：25
    // 解释：
    // 从根到叶子节点路径 1->2 代表数字 12
    // 从根到叶子节点路径 1->3 代表数字 13
    // 因此，数字总和 = 12 + 13 = 25
    static class SumNumbers {
        StringBuilder path = new StringBuilder();
        int res = 0;

        public int sumNumbers(TreeNode root) {
            // 遍历一遍二叉树就能出结果
            traverse(root);
            return res;
        }

        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // 前序遍历位置，记录当前节点值
            path.append(root.val);
            if (root.left == null && root.right == null) {
                // 达到叶子节点，累加路径和
                res += Integer.parseInt(path.toString());
            }
            // 二叉树递归框架，遍历左右子树
            traverse(root.left);
            traverse(root.right);
            // 后序遍历位置，撤销节点值
            path.deleteCharAt(path.length() - 1);
        }
    }

    // 199. 二叉树的右视图
    // 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    // 示例 1:
    // 输入: [1,2,3,null,5,null,4]
    // 输出: [1,3,4]
    // 基本思路：
    // 这题有两个思路：
    // 1、用 BFS 层序遍历算法，每一层的最后一个节点就是二叉树的右侧视图。我们可以把 BFS 反过来，从右往左遍历每一行，进一步提升效率。
    // 2、用 DFS 递归遍历算法，同样需要反过来，先递归 root.right 再递归 root.left，同时用 res 记录每一层的最右侧节点作为右侧视图。
    static class rightSideView1 {
        // BFS层序遍历解法
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            if (root == null) {
                return res;
            }
            // BFS层序遍历，计算右侧视图
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            // while循环控制从上向下一层层遍历
            while (!q.isEmpty()) {
                int sz = q.size();
                // 每一层头部就是最右侧的元素
                TreeNode last = q.peek();
                for (int i = 0; i < sz; i++) {
                    TreeNode cur = q.poll();
                    // 控制每一层从右向左遍历
                    if (cur.right != null) {
                        q.offer(cur.right);
                    }
                    if (cur.left != null) {
                        q.offer(cur.left);
                    }
                }
                res.add(last.val);
            }
            return res;
        }
    }

    static class rightSideView2 {
        // DFS层序遍历解法
        List<Integer> res = new ArrayList<>();
        // 记录递归的层数
        int depth = 0;

        public List<Integer> rightSideView(TreeNode root) {
            traverse(root);
            return res;
        }

        // 二叉树遍历函数
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // 前序遍历位置
            depth++;
            if (res.size() < depth) {
                // 这一层还没有记录值
                // 说明root就是右侧视图的第一个节点
                res.add(root.val);
            }
            // 注意，这里反过来，先遍历右子树再遍历左子树
            // 这样首先遍历的一定是右侧节点
            traverse(root.right);
            traverse(root.left);
            // 后序遍历位置
            depth--;
        }
    }

    // 988. 从叶结点开始的最小字符串
    // 给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
    // 返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
    // 注：字符串中任何较短的前缀在 字典序上 都是 较小 的：
    // 例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。
    // 节点的叶节点是没有子节点的节点。
    // 示例 1：
    // 输入：root = [0,1,2,3,4,3,4]
    // 输出："dba"
    // 示例 2：
    // 输入：root = [25,1,3,1,3,0,2]
    // 输出："adz"
    // 示例 3：
    // 输入：root = [2,2,1,null,1,0,null,0]
    // 输出："abc"
    // 基本思路：
    // 前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维。
    // 代码看起来虽然多，但思路非常简单：用 path 维护递归遍历的路径，到达叶子节点的时候判断字典序最小的路径。
    // 不要忘了在叶子节点的时候也要正确维护 path 变量，而且要把 StringBuilder 中的字符串反转才是题目想要的答案。
    static class SmallestFromLeaf {
        StringBuilder path = new StringBuilder();
        String res = null;

        // 遍历过程中的路径
        public String smallestFromLeaf(TreeNode root) {
            traverse(root);
            return res;
        }

        // 二叉树遍历函数
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                // 找到叶子节点，比较字典序最小的路径
                // 结果字符串是从叶子向根，所以需要反转
                path.append((char) ('a' + root.val));
                path.reverse();

                String s = path.toString();
                if (res == null || res.compareTo(s) > 0) {
                    // 如果字典序更小，则更新res
                    res = s;
                }
                // 恢复，正确维护path中的元素
                path.reverse();
                path.deleteCharAt(path.length() - 1);
                return;
            }
            // 前序位置
            path.append((char) ('a' + root.val));
            traverse(root.left);
            traverse(root.right);
            // 后序位置
            path.deleteCharAt(path.length() - 1);
        }
    }

    // 1022. 从根到叶的二进制数之和
    // 给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
    // 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
    // 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
    // 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
    // 示例 1：
    // 输入：root = [1,0,1,0,1,0,1]
    // 输出：22
    // 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
    // 示例 2：
    // 输入：root = [0]
    // 输出：0
    // 基本思路：
    // 前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「遍历」的思维。
    // 用 path 变量维护每一条从根节点到叶子节点的路径形成的二进制数，到了叶子节点之后将这条路径的二进制数累加到 res 中即可。

    static class SumRootToLeaf {
        int path = 0;
        int res = 0;

        public int sumRootToLeaf(TreeNode root) {
            traverse(root);
            return res;
        }

        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                // 叶子节点
                // 左移操作（path << 1）：左移操作会把path的二进制表示向左移动 1 位，其效果等同于将path乘以 2。
                // 举例来说，要是path的二进制是101（也就是十进制的 5），左移 1 位之后就变成了1010（即十进制的 10）。
                // 按位或操作（| root.val）：按位或操作会把左移后的结果和root.val进行按位或运算。这里要保证root.val的值为 0 或者 1，
                // 这样就能把root.val添加到path二进制表示的最低位。
                // 算术运算实现：path = path * 2 + val;
                res += path << 1 | root.val;
                return;
            }
            // 前序位置
            path = path << 1 | root.val;
            traverse(root.left);
            traverse(root.right);
            // 后序位置
            // 算术运算实现：path = (path - val) / 2;
            path = path >> 1;
        }
    }

    // 1457. 二叉树中的伪回文路径
    // 给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
    // 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
    // 示例 1：
    // 输入：root = [2,3,1,3,1,null,1]
    // 输出：2
    // 解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
    //     在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
    // 思路：如果一组数字中，只有最多一个数字出现的次数为奇数，剩余数字的出现次数均为偶数，那么这组数字可以组成一个回文串。
    static class PseudoPalindromicPaths {
        // 计数数组，题目说了1<=root.val<=9;
        int[] count = new int[10];
        int res = 0;

        public int pseudoPalindromicPaths(TreeNode root) {
            traverse(root);
            return res;
        }

        // 二叉树遍历函数
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                // 遇到叶子节点，判断路径是否为伪回文串
                count[root.val]++;
                // 如果路径上出现奇数次的数字个数大于1
                // 则不可能组成回文串，反之则可以组成回文串
                int odd = 0;
                for (int n : count) {
                    if (n % 2 == 1) { // n % 2 == 1：判断 n 是否为奇数。如果是奇数，则条件成立，odd 计数器加 1。
                        odd++;
                    }
                }
                if (odd <= 1) {
                    res++;
                }
                count[root.val]--;
                return;
            }
            count[root.val]++;
            // 二叉树遍历框架
            traverse(root.left);
            traverse(root.right);
            count[root.val]--;
        }
    }

    // 617. 合并二叉树
    // 给你两棵二叉树： root1 和 root2 。
    // 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。
    // 你需要将这两棵树合并成一棵新二叉树。
    // 合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；
    // 否则，不为 null 的节点将直接作为新二叉树的节点。
    // 返回合并后的二叉树。
    // 注意: 合并过程必须从两个树的根节点开始。
    static class MergeTrees {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null) {
                return root2;
            }
            if (root2 == null) {
                return root1;
            }
            root1.val += root2.val;
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }
    }

    // 【练习】用「遍历」思维解题 II
    // https://labuladong.online/algo/problem-set/binary-tree-traverse-ii/#slug_add-one-row-to-tree

    // 404. 左叶子之和
    // 给定二叉树的根节点 root ，返回所有左叶子之和。
    // 输入: root = [3,9,20,null,null,15,7]
    // 输出: 24
    // 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
    static class SumOfLeftLeaves {
        // 记录左叶子之和
        int sum = 0;

        public int sumOfLeftLeaves(TreeNode root) {
            traverse(root);
            return sum;
        }

        // 二叉树遍历函数
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            if (root.left != null && root.left.left == null && root.left.right == null) {
                // 找到左侧的叶子节点，记录累加值
                sum += root.left.val;
            }
            // 递归框架
            traverse(root.left);
            traverse(root.right);
        }
    }

    // 623. 在二叉树中增加一行
    // 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
    // 注意，根节点 root 位于深度 1 。
    // 加法规则如下:
    // 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
    // cur 原来的左子树应该是新的左子树根的左子树。
    // cur 原来的右子树应该是新的右子树根的右子树。
    // 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
    static class AddOneRow {
        private int targetVal;
        private int targetDepth;

        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            targetVal = val;
            targetDepth = depth;
            // 插入到第一行的话，特殊对待一下
            if (targetDepth == 1) {
                TreeNode newRoot = new TreeNode(targetVal);
                newRoot.left = root;
                return newRoot;
            }
            // 遍历二叉树，走到对应行进行插入
            traverse(root);
            return root;
        }

        private int curDepth = 0;

        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            // 前序遍历
            curDepth++;
            if (curDepth == targetDepth - 1) {
                // 进行插入
                TreeNode newLeft = new TreeNode(targetVal);
                TreeNode newRight = new TreeNode(targetVal);
                newLeft.left = root.left;
                newRight.right = root.right;
                root.left = newLeft;
                root.right = newRight;
            }

            traverse(root.left);
            traverse(root.right);
            // 后序遍历
            curDepth--;
        }
    }

    // 971. 翻转二叉树以匹配先序遍历
    // 给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。
    // 另给你一个由 n 个值组成的行程序列 voyage ，表示 预期 的二叉树 先序遍历 结果。
    // 通过交换节点的左右子树，可以 翻转 该二叉树中的任意节点。例，翻转节点 1 的效果如下：
    // 请翻转 最少 的树中节点，使二叉树的 先序遍历 与预期的遍历行程 voyage 相匹配 。
    // 如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。
    // 示例 1：
    // 输入：root = [1,2], voyage = [2,1]
    // 输出：[-1]
    // 解释：翻转节点无法令先序遍历匹配预期行程。
    // 示例 2：
    // 输入：root = [1,2,3], voyage = [1,3,2]
    // 输出：[1]
    // 解释：交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。
    // 示例 3：
    // 输入：root = [1,2,3], voyage = [1,2,3]
    // 输出：[]
    // 解释：先序遍历已经匹配预期行程，所以不需要翻转节点。
    // 基本思路：
    // 用traverse函数遍历整棵二叉树，对比前序遍历结果，如果节点的值对不上，就无解，如果子树对不上voyage，就尝试反转子树
    static class FlipMatchVoyage {
        List<Integer> res = new LinkedList<>();
        int i = 0;
        int[] voyage;
        boolean canFlip = true;

        public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
            this.voyage = voyage;
            // 遍历的过程中尝试进行反转
            traverse(root);
            if (canFlip) {
                return res;
            }
            return Arrays.asList(-1);
        }

        void traverse(TreeNode root) {
            if (root == null || !canFlip) {
                return;
            }
            if (root.val != voyage[i++]) {
                // 节点的val对不上，必然无解
                canFlip = false;
                return;
            }
            if (root.left != null && root.left.val != voyage[i]) {
                // 前序遍历结果不对，尝试翻转左右子树
                TreeNode temp = root.left;
                root.left = root.right;
                root.right = temp;
                // 记录翻转节点
                res.add(root.val);
            }
            traverse(root.left);
            traverse(root.right);
        }
    }

    // 987. 二叉树的垂序遍历
    // 给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
    // 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
    // 二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
    // 返回二叉树的 垂序遍历 序列。
    // 示例 1：
    // 输入：root = [3,9,20,null,null,15,7]
    // 输出：[[9],[3,15],[20],[7]]
    // 解释：
    // 列 -1 ：只有结点 9 在此列中。
    // 列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
    // 列  1 ：只有结点 20 在此列中。
    // 列  2 ：只有结点 7 在此列中。
    // 示例 2：
    // 输入：root = [1,2,3,4,5,6,7]
    // 输出：[[4],[2],[1,5,6],[3],[7]]
    // 解释：
    // 列 -2 ：只有结点 4 在此列中。
    // 列 -1 ：只有结点 2 在此列中。
    // 列  0 ：结点 1 、5 和 6 都在此列中。
    //           1 在上面，所以它出现在前面。
    //           5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
    // 列  1 ：只有结点 3 在此列中。
    // 列  2 ：只有结点 7 在此列中。
    // 基本思路：
    // 看这题的难度是困难，但你别被吓住了，我们从简单的开始，如果以整棵树的根节点为坐标 (0, 0)，你如何打印出其他节点的坐标？
    void traverse(TreeNode root, int row, int col) {
        if (root == null) {
            return;
        }
        System.out.println("row = " + row + ", col = " + col);
        traverse(root.left, row+1, col-1);
        traverse(root.right, row+1, col+1);
        // 然后就简单了，把这些坐标收集起来，依据题目要求进行排序，组装成题目要求的返回数据格式即可。
    }

    static class VerticalTraversal{
        // 记录每个节点和对应的坐标 (row, col)
        class Triple {
            public int row, col;
            public TreeNode node;

            public Triple(TreeNode node, int row, int col) {
                this.node = node;
                this.row = row;
                this.col = col;
            }
        }

        public List<List<Integer>> verticalTraversal(TreeNode root) {
            // 遍历二叉树，并且为所有节点生成对应的坐标
            traverse(root, 0, 0);
            // 根据题意，根据坐标值对所有节点进行排序：
            // 按照 col 从小到大排序，col 相同的话按 row 从小到大排序，
            // 如果 col 和 row 都相同，按照 node.val 从小到大排序。
            nodes.sort((Triple a, Triple b) -> {
                if (a.col == b.col && a.row == b.row) {
                    return a.node.val - b.node.val;
                }
                if (a.col == b.col) {
                    return a.row - b.row;
                }
                return a.col - b.col;
            });
            // 将排好序的节点组装成题目要求的返回格式
            LinkedList<List<Integer>> res = new LinkedList<>();
            // 记录上一列编号，初始化一个特殊值
            int preCol = Integer.MIN_VALUE;
            for (int i = 0; i < nodes.size(); i++) {
                Triple cur = nodes.get(i);
                if (cur.col != preCol) {
                    // 开始记录新的一列
                    res.addLast(new LinkedList<>());
                    preCol = cur.col;
                }
                res.getLast().add(cur.node.val);
            }

            return res;
        }

        ArrayList<Triple> nodes = new ArrayList<>();
        // 二叉树遍历函数，记录所有节点对应的坐标
        void traverse(TreeNode root, int row, int col) {
            if (root == null) {
                return;
            }
            // 记录坐标
            nodes.add(new Triple(root, row, col));
            // 二叉树遍历框架
            traverse(root.left, row + 1, col - 1);
            traverse(root.right, row + 1, col + 1);
        }
    }

    // 【练习】用「分解问题」思维解题 I
    // https://labuladong.online/algo/problem-set/binary-tree-divide-i/
    // 331. 验证二叉树的前序序列化
    // 序列化二叉树的一种方法是使用 前序遍历 。
    // 当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
    // 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
    // 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
    // 保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
    // 你可以认为输入格式总是有效的
    // 例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
    // 注意：不允许重建树。
    // 示例 1:
    // 输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
    // 输出: true
    // 示例 2:
    // 输入: preorder = "1,#"
    // 输出: false
    // 示例 3:
    // 输入: preorder = "9,#,#,1"
    // 输出: false

    static class IsValidSerialization{
        public boolean isValidSerialization(String preorder) {
            // 将字符串转化成列表
            LinkedList<String> nodes = new LinkedList<>();
            for(String s : preorder.split(",")){
                nodes.addLast(s);
            }
            return deserialize(nodes) && nodes.isEmpty();
        }

        boolean deserialize(LinkedList<String> nodes){
            if (nodes.isEmpty()){
                return false;
            }
            // ***** 前序遍历位置 *****
            // 列表最左侧就是根节点
            String first = nodes.removeFirst();
            if (first.equals("#")){
                return true;
            }
            // *********************

            // 第一次调用：验证左子树的合法性。
            // 第二次调用：验证右子树的合法性。
            // 使用 && 连接：确保左右子树都合法，且处理完所有节点（列表为空）。
            return deserialize(nodes) && deserialize(nodes);
        }
    }

}






























